考试的时候写了3.5h , 考后又写了2h 才过掉。
每次修改只会影响两个矩阵,可以暴力计算。
我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。
因为有散段所以考虑用线段树维护区间矩阵的乘法,整段直接矩阵快速幂
但要注意修改操作相邻时影响的矩阵会重复,可以存进 vector 里暴力修改后一起乘。
代码大部分是考场写的,太丑就不放了。虽然口胡很简单但是写起来是真的恶心。
An Ac a day, keeps the doctor away!
考试的时候写了3.5h , 考后又写了2h 才过掉。
每次修改只会影响两个矩阵,可以暴力计算。
我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。
因为有散段所以考虑用线段树维护区间矩阵的乘法,整段直接矩阵快速幂
但要注意修改操作相邻时影响的矩阵会重复,可以存进 vector 里暴力修改后一起乘。
代码大部分是考场写的,太丑就不放了。虽然口胡很简单但是写起来是真的恶心。
扫码打赏,你说多少就多少
打开微信扫一扫,即可进行扫码打赏哦